//成功自己写出来一遍，所以，我该怎么把递推公式转化成矩阵呢？这个又适合什么情况呢？好费解啊。
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int x = 2;//所有矩阵都是x*x 的矩阵
struct matrix{
	ll a[2][2];
	
};
matrix matrix_mul(matrix A,matrix B,int mod);
matrix matrix_pow(matrix A,ll n,int mod);
matrix unit();
ll fib(ll n,int mod);
int main(){
	ll n,m;
	cin>>n>>m;
	fib(n,m);
	return 0;
	
}matrix matrix_mul(matrix A,matrix B,int mod){
	matrix C;
	for(int i = 0;i<x;++i){
		for(int j = 0;j<x;++j){
			C.a[i][j] = 0;
			for(int k = 0;k<x;++k){
				//c00=a00*b00+a01*b10		
				//c01=a00*b01+a01*b11	
				C.a[i][j]+=A.a[i][k]*B.a[k][j]%mod;
				C.a[i][j]%=mod;
				
			}
		}
	}return C;
	
}matrix unit(){
	matrix res;
	for(int i = 0;i<x;++i){
		for(int j = 0;j<x;++j){
			if(i==j)
				res.a[i][j] = 1;
			else 
				res.a[i][j] = 0;
			
		}
	}return res;
	
}matrix matrix_pow(matrix A,ll n,int mod){
	matrix res = unit(),temp = A;
	for(;n;n/=2){
		if(n&1){
			res = matrix_mul(res,temp,mod);
			
		}temp = matrix_mul(temp,temp,mod);
		
	}return res;
	
}ll fib(ll n,int mod){
	matrix res,A,B;
	res.a[0][0] = 1;
	res.a[0][1] = 1;
	res.a[1][0] = 1;
	res.a[1][1] = 0;
	A = res;
	A.a[0][1] = 0;
	res = matrix_pow(res,n-1,mod);
	cout<<matrix_mul(res,A,mod).a[1][0];
	
}

